0-1 背包和完全背包的差別在於：東西是不是可以重複拿取。如果可以取多次的話，一個物品取不同次的情況也要一併考慮進去。

279. Perfect Squares 這題需要先把題目轉成 dp 相關概念再去解，這邊遵循 dp 的慣例，一個維度放可選取的物品數，另一個維度記錄 weight（選取的數字總和），而 value 則代表在目前的 weight 下的最佳解（該數字最少可以由幾個平方數組成）。value 和以前習慣的有點不同，我們希望越小越好。

而遵照上面的規則不停比較、記錄優化結果，最後就可以得到答案了。

class Solution:
    def numSquares(self, n: int) -> int:
        arr = [i for i in range(n+1)]
        mx = int(sqrt(n))
        item = [i**2 for i in range(1, mx+1)]

        for i in range(len(item)):
            tmp = item[i]
            j = tmp
            while j <= n:
                arr[j] = min(arr[j], arr[j-tmp]+1)
                j += 1
        
        return arr[-1]

• 完全背包
  • 279. Perfect Squares
  • 322. Coin Change

• Total Count: 12
  • 是說今天晚上有一陣子鐵人邦掛掉（是在更新嗎），一整個驚嚇到不行QQ